Miért gyorsabb a rendezett tömb feldolgozása, mint a nem rendezett tömb feldolgozása?

Áldozata vagy az elõrejelzés kudarcának.
Mi a fiókjóslás?
Vegyünk egy vasúti csomópontot:
Kép: Mecanismo, a Wikimedia Commons-on keresztül. CC-By-SA 3.0 licenc alatt használják.
Most az érvelés kedvéért tegyük fel, hogy ez még az 1800-as években történt - a távolsági vagy rádiós kommunikáció előtt.
Ön egy csomópont üzemeltetője, és hallja a vonat érkezését. Fogalmad sincs, melyik útnak kellene állnia. Megállítja a vonatot, hogy megkérdezze a vezetőt, melyik irányba akarnak. És akkor megfelelően beállítja a kapcsolót.
A vonatok nehézek és sok tehetetlenséggel rendelkeznek. Tehát örökké tartanak, hogy elinduljanak és lassítsanak.
Van jobb módszer? Kitalálod, melyik irányba halad a vonat!
Ha jól sejtette, folytatódik.
Ha rosszul sejtette, a kapitány megáll, visszaáll és kiabál, hogy fordítsa meg a kapcsolót. Ezután újraindulhat a másik úton.
Ha minden alkalommal jól sejted, a vonatnak soha nem kell megállnia. Ha túl gyakran gondolja rosszul, a vonat sok időt fog megtenni megállással, biztonsági mentéssel és újraindítással.
Vegyünk egy if-utasítást: Processzor szinten ez egy elágazási utasítás:
Ön processzor, és lát egy ágat. Fogalmad sincs, melyik irányba fog haladni. Mit csinálsz? Leállítja a végrehajtást és megvárja, amíg az előző utasítások teljesülnek. Ezután folytatja a helyes utat.
A modern processzorok bonyolultak és hosszú csővezetékekkel rendelkeznek. Tehát örökké tartanak a "bemelegítés" és a "lelassítás".
Van jobb módszer? Kitalálod, hogy az ág melyik irányba fog haladni!
Ha jól sejtette, folytatja a végrehajtást.
Ha rosszul sejtette, le kell öblítenie a csővezetéket és vissza kell gördülnie az ághoz. Ezután újraindíthatja a másik utat.
Ha minden alkalommal jól sejted, a végrehajtásnak soha nem kell leállnia. Ha túl gyakran hibázol, sok időt töltesz elakadással, visszagurítással és újraindítással.
Ez elágazási jóslat. Elismerem, hogy ez nem a legjobb hasonlat, mivel a vonat csak egy zászlóval tudta jelezni az irányt. De a számítógépeknél a processzor az utolsó pillanatig nem tudja, hogy melyik ág megy tovább.
Tehát hogyan gondolná stratégiailag, hogy minimalizálja azt a számot, amikor a vonatnak vissza kell lépnie és le kell mennie a másik úton? Megnézed a múlt történetét! Ha a vonat az idő 99% -ában balra megy, akkor azt hiszed, hogy elment. Ha váltakozik, akkor váltogatja a találgatásokat. Ha háromszor egy irányba megy, akkor ugyanazt gondolja ...
Más szavakkal, megpróbál azonosítani egy mintát és követni. Nagyjából így működnek az elágazó prediktorok.
A legtöbb alkalmazás jól viselkedő ágakkal rendelkezik. Tehát a modern ágazati előrejelzők általában meghaladják a 90% -os találati arányt. De ha kiszámíthatatlan, felismerhetetlen mintákkal nem rendelkező ágakkal szembesülnek, az ágjelzők gyakorlatilag haszontalanok.
További olvasmány: "Ág prediktor" cikk a Wikipédián.
Amint fentről sejtettük, a bűnös ez az if-állítás:
if (adatok [c]> = 128)
összeg + = adatok [c];
Figyelje meg, hogy az adatok egyenletesen oszlanak meg 0 és 255 között. Az adatok rendezése után nagyjából az iterációk első fele nem írja be az if-utasítást. Ezt követően mindannyian beírják az if-utasítást.
Ez nagyon barátságos az ág előrejelzője számára, mivel az ág egymás után sokszor ugyanabba az irányba megy. Még egy egyszerű telítőszámláló is pontosan megjósolja az elágazást, leszámítva azt a néhány iterációt, amelyik irányváltást követ.
Gyors megjelenítés:
T = levett ág
N = el nem vett ág
adatok [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
ág = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNNTTTTTTT ... TTTTTTTTTT (könnyen megjósolható)
Ha azonban az adatok teljesen véletlenszerűek, akkor az elágazás-előrejelző használhatatlanná válik, mert nem tudja megjósolni a véletlenszerű adatokat. Így valószínűleg körülbelül 50% -os hibás megjóslás lesz (nem jobb, mint a véletlenszerű találgatás).
adatok [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
elágazás = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (teljesen véletlenszerű - nehéz megjósolni)
Tehát mit lehet tenni?
Ha a fordító nem tudja optimalizálni az ágat egy feltételes lépéshez, akkor próbáljon meg néhány feltörést, ha hajlandó feláldozni az olvashatóságot a teljesítmény érdekében.
Cserélje ki:
if (adatok [c]> = 128)
összeg + = adatok [c];
val vel:
int t = (adatok [c] - 128) >> 31;
összeg + = ~ t & adatok [c];
Ez kiküszöböli az elágazást, és néhány bitenkénti művelettel helyettesíti.
(Ne feledje, hogy ez a feltörés nem szigorúan egyenértékű az eredeti if-utasítással. De ebben az esetben ez az adatok összes bemeneti értékére érvényes [].)
Referenciaértékek: Core i7 920, 3,5 GHz
C ++ - Visual Studio 2010 - x64 kiadás
// Ág - Véletlenszerű
másodperc = 11,777
// Ág - rendezve
másodperc = 2,352
// Ág nélküli - Véletlenszerű
másodperc = 2,564
// Ág nélküli - Rendezve
másodperc = 2,587
Java - NetBeans 7.1.1 JDK 7 - x64
// Ág - Véletlenszerű
másodperc = 10,93293813
// Ág - rendezve
másodperc = 5.643797077
Ág nélküli -Véletlen
másodperc = 3,113581453
// Ág nélküli - Rendezve
másodperc = 3,186068823
Megfigyelések:
A fiókteleppel: Óriási különbség van a rendezett és a nem rendezett adatok között.
A Hack segítségével: Nincs különbség a rendezett és a nem rendezett adatok között.
C ++ esetben a hack valójában egy kicsit lassabb, mint az ág esetén, amikor az adatokat rendezik.
Általános ökölszabály, hogy elkerüljük az adatfüggő elágazásokat a kritikus hurokban (például ebben a példában).
Frissítés:
A GCC 4.6.1 -03 vagy -ftree-vektorizációval x64-en képes feltételes mozgást generálni. Tehát nincs különbség a rendezett és a nem rendezett adatok között - mindkettő gyors.
(Vagy kissé gyorsan: a már rendezett esetben a cmov lassabb lehet, különösen, ha a GCC a kritikus útvonalra helyezi, ahelyett, hogy csak hozzáadná, főleg az Intel-nél a Broadwell előtt, ahol a cmov-nak 2 ciklusi késleltetése van: a gcc optimalizálási jelző -O3 lassabbá teszi a kódot mint -O2)
A VC ++ 2010 még az / Ox alatt sem képes feltételes mozgásokat generálni ehhez az ághoz.
Az Intel C ++ Compiler (ICC) 11 valami csodát tesz. Felcseréli a két hurkot, ezáltal a kiszámíthatatlan ágat a külső hurokhoz emeli. Tehát nemcsak immúnis a téves előrejelzésekre, hanem kétszer olyan gyors is, mint amit a VC ++ és a GCC képes generálni! Más szavakkal, az ICC kihasználta a teszt-ciklust, hogy legyőzze a referenciaértéket ...
Ha megadja az Intel fordítónak az ág nélküli kódot, akkor az csak jobbra vektorizálja ... és ugyanolyan gyors, mint az elágazásnál (a hurokcserével).
Ez azt mutatja, hogy még a kiforrott, modern fordítók is nagyban változhatnak a kód optimalizálásában ...
|
Ág jóslat.
Rendezett tömb esetén a [c]> = 128 feltételadatok először hamisak egy értékcsíkra, majd minden későbbi értékre igazak lesznek. Ezt könnyű megjósolni. Válogatás nélküli tömböt fizet az elágazási költségért.
|
A teljesítmény drasztikus javulása az adatok rendezése során az, hogy az ág-előrejelzési büntetést eltávolítják, amint ezt a Mysticial válasza szépen elmagyarázta.
Most, ha megnézzük a kódot
if (adatok [c]> = 128)
összeg + = adatok [c];
megállapíthatjuk, hogy ennek a bizonyos, ha ... másnak ... ágnak az a jelentése, hogy valamit hozzáadunk, ha egy feltétel teljesül. Ez az elágazástípus könnyen átalakítható feltételes mozgás utasítássá, amelyet x86 rendszerben feltételes mozgatási utasítássá állítanának össze: cmovl. Az elágazás és így a potenciális elágazás-előrejelzési büntetés megszűnik.
C-ben, tehát C ++ -ban az utasítás, amely közvetlenül (optimalizálás nélkül) fordítaná az x86-os feltételes mozgás utasításba, a terner operátor ...? ...: .... Tehát átírjuk a fenti állítást egyenértékűvé:
összeg + = adatok [c]> = 128? adatok [c]: 0;
Az olvashatóság fenntartása mellett ellenőrizhetjük a gyorsítási tényezőt.
3,4 GHz-es Intel Core i7-2600K és Visual Studio 2010 kiadási mód esetén a referenciaérték (a formátumot a Mysticialról másolta):
x86
// Ág - Véletlenszerű
másodperc = 8,885
// Ág - rendezve
másodperc = 1,528
// Ág nélküli - Véletlenszerű
másodperc = 3,716
// Ág nélküli - Rendezve
másodperc = 3,71
x64
// Ág - Véletlenszerű
másodperc = 11,302
// Ág - rendezve
másodperc = 1,830
// Ág nélküli - Véletlenszerű
másodperc = 2,736
// Ág nélküli - Rendezve
másodperc = 2,737
Az eredmény több tesztben is robusztus. Nagy sebességet kapunk, ha kiszámíthatatlan az elágazási eredmény, de egy kicsit szenvedünk, ha kiszámítható. Valójában egy feltételes lépés használata esetén a teljesítmény az adatmintától függetlenül azonos.
Most nézzük meg alaposabban az általuk generált x86-os összeállítást. Az egyszerűség kedvéért két max1 és max2 függvényt használunk.
A max1 a feltételes elágazást használja, ha ... egyebet ...:
int max1 (int a, int b) {
ha (a> b)
vissza egy;
más
visszatérés b;
}
A max2 a ternáris operátort használja ...? ...: ...:
int max2 (int a, int b) {
vissza a> b? a: b;
}
Egy x86-64-es gépen a GCC -S generálja az alábbi összeállítást.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
elhagy
ret
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
elhagy
ret
A max2 sokkal kevesebb kódot használ a cmovge utasítások miatt. De az igazi nyereség az, hogy a max2 nem jár águgrásokkal, jmp-vel, aminek jelentős teljesítménybüntetése lenne, ha az előre jelzett eredmény nem megfelelő.
Tehát miért teljesít jobban egy feltételes lépés?
Egy tipikus x86-os processzorban az utasítás végrehajtása több szakaszra oszlik. Nagyjából különböző hardverekkel rendelkezünk a különböző szakaszok kezeléséhez. Tehát nem kell várnunk egy utasítás befejezésére, hogy elindítsunk egy újat. Ezt nevezzük pipeliningnek.
Elágazási esetben a következő utasítást az előző határozza meg, ezért nem tudjuk elvégezni a csővezeték-vezetést. Vagy várnunk kell, vagy megjósolni.
Feltételes lépés eseténa végrehajtás feltételes lépés utasítása több szakaszra oszlik, de a korábbi szakaszok, mint például a Fetch és a Decode, nem függenek az előző utasítás eredményétől; csak az utóbbi szakaszoknak kell az eredmény. Így egy utasítás végrehajtási idejének töredékét várjuk meg. Ezért a feltételes mozgás verzió lassabb, mint az elágazás, amikor a jóslat könnyű.
A Computer Systems: A Programmer Perspective második kiadás ezt részletesen elmagyarázza. Ellenőrizheti a Feltételes mozgatási utasítások 3.6.6 szakaszát, a processzor architektúrájának teljes 4. fejezetét, az ágakra vonatkozó előrejelzési és hibás megjóslási büntetések speciális kezelését az 5.11.2 szakaszban.
Néha egyes modern fordítók jobb teljesítménnyel optimalizálhatják kódunkat összeállításra, néha egyes fordítók nem (a kérdéses kód a Visual Studio natív fordítóját használja). Ha ismerjük az elágazás és a feltételes lépés közötti teljesítménykülönbséget, ha az kiszámíthatatlan, akkor jobb kódot írhatunk, ha a forgatókönyv annyira összetetté válik, hogy a fordító nem tudja automatikusan optimalizálni őket.
|
Ha kíváncsi a kód további optimalizálására, fontolja meg ezt:
Az eredeti hurokkal kezdve:
for (aláíratlan i = 0; i <100000; ++ i)
{
for (aláíratlan j = 0; j  = 128)
összeg + = adat [j];
}
}
A hurokcserével biztonságosan megváltoztathatjuk ezt a kört:
for (aláíratlan j = 0; j  = 128)
összeg + = adat [j];
}
}
Ezután láthatja, hogy az if feltétel feltétel állandó az i hurok végrehajtása során, így felemelheti az if kimenetet:
for (aláíratlan j = 0; j  = 128)
{
for (aláíratlan i = 0; i <100000; ++ i)
{
összeg + = adat [j];
}
}
}
Ezután látja, hogy a belső hurok egyetlen kifejezésre bontható, feltéve, hogy a lebegőpontos modell lehetővé teszi (/ fp: például a gyors dobás)
for (aláíratlan j = 0; j  = 128)
{
összeg + = adat [j] * 100000;
}
}
Ez 100 000-szer gyorsabb, mint korábban.
|
Kétségtelen, hogy néhányunkat érdekelnek a CPU elágazás-előrejelzője számára problematikus kód azonosításának módjai. A Valgrind eszköz cachegrind rendelkezik egy elágazás-előrejelző szimulátorral, amely a --branch-sim = yes jelző használatával engedélyezett. Az ebben a kérdésben szereplő példákon történő futtatása, a külső hurkok számának 10000-ra csökkentésével és a g ++ -val való összeállításával a következő eredményeket adja:
Rendezés:
== 32551 == Fiókok: 656 645 130 (656 609 208 kondíció + 35 922 ind)
== 32551 == Tévedések: 169 556 (169 095 kondíció + 461 ind)
== 32551 == Hibásan kiszámított arány: 0,0% (0,0% + 1,2%)
Válogatás nélkül:
== 32555 == Ágak: 655 996 082 (655 960 160 kondíció + 35 922 ind)
== 32555 == Tévedések: 164 073 152 (164 072 692 feltétel + 460 ind)
== 32555 == Hibásan kiszámított arány: 25,0% (25,0% + 1,2%)
A cg_annotate által létrehozott soronkénti kimenetre fúrva a kérdéses hurkot látjuk:
Rendezés:
Bc Bcm Bi Bim
10 001 4 0 0 (aláíratlan i = 0; i <10000; ++ i)
. . . . {
. . . . // elsődleges hurok
327 690 000 10 016 0 0 (aláíratlan c = 0; c  = 128)
0 0 0 0 összeg + = adatok [c];
. . . . }
. . . . }
Válogatás nélkül:
Bc Bcm Bi Bim
10 001 4 0 0 (aláíratlan i = 0; i <10000; ++ i)
. . . . {
. . . . // elsődleges hurok
327 690 000 10 038 0 0 (aláíratlan c = 0; c  = 128)
0 0 0 0 összeg + = adatok [c];
. . . . }
. . . . }
Ez lehetővé teszi a problémás vonal egyszerű azonosítását - a válogatás nélküli verzióban az if (data [c]> = 128) sor 164 050 007 rosszul megjósolt feltételes elágazást (Bcm) okoz a cachegrind ág-előrejelző modellje alatt, míg a rendezett verzióban csak 10 006-ot okoz. .
Alternatív megoldásként Linuxon a teljesítményszámláló alrendszert használhatja ugyanazon feladat végrehajtására, de natív teljesítménnyel a CPU számlálókkal.
perf stat ./sumtest_sorted
Rendezés:
Teljesítményszámláló statisztika a „./sumtest_sorted” számára:
11808.095776 feladat-óra # 0.998 CPU-t használtak
1062 környezetkapcsoló # 0,090 K / sec
14 CPU-migráció # 0,001 K / sec
337 oldalhiba # 0,029 K / sec
26 487 882 764 ciklus # 2,243 GHz
41 025 654 322 utasítás # 1,55 insns ciklusonként
6 558 871 379 ág # 555,455 M / sec
567.204 ág-hiányzik az összes ág 0,01% -a
11,827228330 másodperc telt el
Válogatás nélkül:
Teljesítmény„./sumtest_unsorted” számlálók:
28877.954344 task-clock # 0.998 CPU-t használtak
2 584 kontextuskapcsoló # 0,089 K / sec
18 CPU-migráció # 0,001 K / sec
335 oldalhiba # 0,012 K / sec
65 076 127 795 ciklus # 2,253 GHz
41 032 528 741 utasítás # 0,63 inns ciklusonként
6 560 579 013 ág # 227,183 M / sec
1 646 394 749 elágazás hiányzik az összes ág 25,10% -a
28,935500947 másodperc telt el
A forráskód kommentárját szétszereléssel is elvégezheti.
tökéletes lemez -e ág-hiányzik ./sumtest_sortálatlan
perf jegyzet -d sumtest_ válogatatlan
Százalék | Forráskód és a sumtest_unsorted szétszerelése
------------------------------------------------
...
: összeg + = adatok [c];
0,00: 400a1a: mov -0x14 (% rbp),% eax
39.97: 400a1d: mov% eax,% eax
5.31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4,60: 400a26: cltq
0,00: 400a28: add% rax, -0x30 (% rbp)
...
További részletekért lásd a teljesítmény oktatóanyagot.
|
Most olvastam fel ezt a kérdést és válaszait, és úgy érzem, hogy hiányzik egy válasz.
Az ágak előrejelzésének megszüntetésének egyik általános módja, amelyről azt találtam, hogy a kezelt nyelveken különösen jól működik, a táblázatkeresés ahelyett, hogy elágazást használna (bár ebben az esetben még nem teszteltem).
Ez a megközelítés általában akkor működik, ha:
ez egy kicsi asztal, és valószínűleg a processzor tárolja, és
elég szűk körben futtatja a dolgokat, és / vagy a processzor előre betöltheti az adatokat.
Háttér és miért
A processzor szempontjából a memóriája lassú. A sebességkülönbség kiegyenlítésére a processzorba beépítenek pár gyorsítótárat (L1 / L2 gyorsítótár). Tehát képzelje el, hogy szép számításokat végez, és kitalálja, hogy szüksége van egy darab memóriára. A processzor megkapja a „betöltés” ​​műveletét, és betölti a memória egy részét a gyorsítótárba - majd a cache segítségével elvégzi a többi számítást. Mivel a memória viszonylag lassú, ez a "terhelés" lelassítja a programot.
Az ágak jóslásához hasonlóan ezt optimalizálták a Pentium processzorokban is: a processzor azt jósolja, hogy be kell töltenie egy adatot, és megkísérli betölteni ezt a gyorsítótárba, mielőtt a művelet valóban elérné a gyorsítótárat. Mint már láttuk, az elágazás-előrejelzés néha borzasztóan rosszul megy - a legrosszabb esetben vissza kell térnie, és meg kell várnia a memória betöltését, amely örökké fog tartani (más szavakkal: a meghibásodott elágazás-előrejelzés rossz, egy memória az ág-előrejelzés kudarca utáni terhelés egyszerűen szörnyű!).
Szerencsénkre, ha a memória hozzáférési mintája kiszámítható, a processzor betölti a gyorsítótárába, és minden rendben van.
Az első dolog, amit tudnunk kell, mi a kicsi? Míg a kisebb általában jobb, az az alapszabály, hogy ragaszkodni kell a <= 4096 bájt méretű keresőtáblákhoz. Felső határként: ha a keresőtábla nagyobb, mint 64K, akkor valószínűleg érdemes újragondolni.
Táblázat összeállítása
Tehát rájöttünk, hogy létrehozhatunk egy kis asztalt. A következő tennivaló egy keresési funkció helyére állítása. A keresési függvények általában olyan kicsi függvények, amelyek néhány alapvető egész műveletet használnak (és, vagy, xor, shift, összeadás, eltávolítás és esetleg szorzás). Azt szeretné, hogy a keresési funkció lefordítsa a bemenetet valamiféle „egyedi kulcsra” a táblázatban, amely ezután egyszerűen megadja a választ arra a munkára, amelyet el akart végezni.
Ebben az esetben:> = 128 azt jelenti, hogy megtarthatjuk az értéket, <128 azt jelenti, hogy megszabadulunk tőle. Ennek legegyszerűbb módja az „AND” használata: ha megtartjuk, akkor mi ÉS a 7FFFFFFF-el; ha meg akarunk szabadulni tőle, akkor azt ÉS 0-val vesszük észre. Figyeljük meg azt is, hogy a 128 2-es hatvány - így előre mehetünk és elkészíthetünk egy 32768/128 egész számból álló táblázatot, és kitölthetünk egy nulla és sok 7FFFFFFFF.
Kezelt nyelvek
Kíváncsi lehet, hogy ez miért működik jól a kezelt nyelveken. Végül is a kezelt nyelvek egy ággal ellenőrzik a tömbök határait, hogy megbizonyosodjanak róla, hogy nem kavarodnak el ...
Nos, nem pontosan ... :-)
Elég sok munka történt ezen ág felszámolásával a kezelt nyelvek esetében. Például:
for (int i = 0; i  = 128)? c: 0;
}
// Teszt
DateTime startTime = System.DateTime.Now;
hosszú összeg = 0;
for (int i = 0; i <100000; ++ i)
{
// Elsődleges hurok
for (int j = 0; j  = 128. értékek érdekelnek. Ez azt jelenti, hogy könnyen kivonhatunk egyetlen bitet, amely megmondja, hogy akarunk-e értéket vagy sem: eltolással a jobb 7 bitből álló adatok, 0 vagy 1 bit marad, és csak akkor szeretnénk hozzáadni az értéket, ha 1 bitünk van. Nevezzük ezt a bitet "döntési bitnek".
Ha a döntési bit 0/1 értékét indexként használjuk egy tömbben, akkor olyan kódot készíthetünk, amely ugyanolyan gyors lesz, függetlenül attól, hogy az adatokat rendezik-e vagy sem. Kódunk mindig ad hozzá értéket, de ha a döntési bit 0, akkor hozzáadjuk az értéket valahol, ami nem érdekel. Itt van a kód:
// Teszt
óra_t indítás = óra ();
hosszú hosszú a [] = {0, 0};
hosszú hosszú összeg;
for (aláíratlan i = 0; i <100000; ++ i)
{
// Elsődleges hurok
for (aláíratlan c = 0; c > 7);
a [j] + = adat [c];
}
}
double elapsedTime = static_cast  (óra () - start) / CLOCKS_PER_SEC;
összeg = a [1];
Ez a kód elvesztegeti az összeadások felét, de soha nem rendelkezik elágazás-előrejelzési hibával. Rendkívül gyorsabb a véletlenszerű adatoknál, mint a tényleges if utasítással ellátott verzió.
De tesztelésem során az explicit keresőtábla ennél valamivel gyorsabb volt, valószínűleg azért, mert a keresőtáblába történő indexelés valamivel gyorsabb volt, mint a biteltolás. Ez megmutatja, hogy a kódom hogyan állítja be és használja a keresőtáblát (a kódban elképzelhetetlenül lut-nak hívják a "LookUp Table" -t). Itt van a C ++ kód:
// Nyújtsa be, majd töltse ki a keresési táblázatot
int lut [256];
for (aláíratlan c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// A felépítés után használja a keresőtáblát
for (aláíratlan i = 0; i <100000; ++ i)
{
// Elsődleges hurok
for (aláíratlan c = 0; c  érték)
csomópont = csomópont-> pBal;
más
csomópont = csomópont-> pRight;
ez a könyvtár valami hasonlót tenne:
i = (x  érték);
csomópont = csomópont-> link [i];
Itt van egy link erre a kódra: Piros fekete fák, örökké zavartan
|
Rendezett esetben jobban tehet, mint a sikeres elágazás-előrejelzésre vagy bármely ág nélküli összehasonlítási trükkre hagyatkozni: teljesen távolítsa el az elágazást.
Valójában a tömböt egy összefüggő zónában particionálják, ahol az adatok <128, a másikban pedig az adatok> = 128. Tehát meg kell találni a partíciópontot dichotomikus kereséssel (Lg (arraySize) = 15 összehasonlítás segítségével), majd egyenes felhalmozást kell végrehajtani az a pont.
Valami (nem ellenőrzött)
int i = 0, j, k = tömbSize;
míg (i > 1;
if (adatok [j]> = 128)
k = j;
más
i = j;
}
összeg = 0;
for (; i > 1;
for (i = 0, k = arraySize; i  = 128? k: i) = j)
j = (i + k) >> 1;
for (összeg = 0; i  = 128)
/ \
/ \
/ \
igaz hamis
/ \
/ \
/ \
/ \
B) összeg + = adatok [c]; C) hurokhoz vagy nyomtatáshoz ().
Elágazás-előrejelzés nélkül a következők történnének:
A B vagy C utasítás végrehajtásához a processzornak meg kell várnia, amíg az A utasítás el nem éri a csővezeték EX szakaszát, mivel a B vagy a C utasításra való áttérés döntése az A utasítás eredményétől függ. így fog kinézni.
amikor a feltétel igazra tér vissza:
Mikor, ha a feltétel hamis eredményt ad:
Az A utasítás eredményére való várakozás eredményeként a fenti esetben az összes CPU-ciklus eltöltött (elágazás-előrejelzés nélkül; igaz és hamis esetén is) 7.
Mi tehát az elágazás-jóslat?
Az elágazás előrejelzője megpróbálja kitalálni, hogy egy elágazás (ha-akkor-más struktúra) milyen irányba halad, mielőtt ez biztosan megismerhető lenne. Nem várja meg, amíg az A utasítás eléri a csővezeték EX szakaszát, de kitalálja a döntést, és továbblép az utasításhoz (példánk esetében B vagy C).
Helyes találgatás esetén a csővezeték így néz ki:
Ha később kiderül, hogy a találgatás téves volt, akkor a részben végrehajtott utasításokat a rendszer elveti, és a folyamat a megfelelő elágazással kezdődik, késleltetéssel.
Az elágazások hibás előrejelzése esetén pazarolt idő megegyezik a csővezeték szakaszainak számával a beolvasási és a végrehajtási szakasz között. A modern mikroprocesszorok általában meglehetősen hosszú csővezetékekkel rendelkeznek, így a hibás előrejelzés késleltetése 10 és 20 óra között van. Minél hosszabb a csővezeték, annál nagyobb szükség van egy jó elágazás-előrejelzőre.
Az OP kódjában a feltételes első alkalommal az elágazás előrejelzőnek nincs semmilyen információja a jóslás megalapozásához, ezért először véletlenszerűen választja ki a következő utasítást. A for ciklus későbbi részében az előrejelzést a történelemre alapozhatja.
A növekvő sorrendben rendezett tömb esetében három lehetőség áll rendelkezésre:
Az összes elem kevesebb, mint 128
Az összes elem nagyobb, mint 128
Egyes kezdő új elemek száma kevesebb, mint 128, később pedig nagyobb lesz, mint 128
Tegyük fel, hogy a prediktor az első menetben mindig az igaz elágazást fogja feltételezni.
Tehát az első esetben mindig az igaz leszág, mivel történelmileg minden jóslata helytálló.
A 2. esetben kezdetben rosszat fog megjósolni, de néhány ismétlés után helyesen fog megjósolni.
A harmadik esetben kezdetben helyesen fog megjósolni, amíg az elemek kevesebbek lesznek, mint 128. Ezután egy ideig meghibásodik, és maga a helyes, ha az ág előrejelzési hibáját látja a történelemben.
Mindezekben az esetekben a meghibásodás száma túl kevés lesz, és ennek következtében csak néhányszor kell elvetnie a részben végrehajtott utasításokat, és a megfelelő elágazással kell kezdeni, kevesebb CPU-ciklust eredményezve.
De véletlenszerű válogatás nélküli tömb esetén az előrejelzésnek el kell vetnie a részben végrehajtott utasításokat, és legtöbbször a megfelelő ággal kell kezdeni, és több CPU-ciklust kell eredményeznie a rendezett tömbhöz képest.
|
Hivatalos válasz:
Intel - Az ágak téves megjóslásának elkerülése
Intel - Ágazatok és hurkok átszervezése a tévedések megelőzése érdekében
Tudományos cikkek - elágazási előrejelző számítógépes architektúra
Könyvek: J.L. Hennessy, D.A. Patterson: Számítógép-architektúra: kvantitatív megközelítés
Cikkek tudományos publikációkban: T.Y. Igen, Y.N. Patt sok ilyet tett az ág jóslatain.
Ebből a kedves ábrából azt is láthatja, hogy az ág prediktor miért keveredik össze.
Az eredeti kód minden eleme véletlenszerű érték
adatok [c] = std :: rand ()% 256;
így a prediktor az std :: rand () fújásakor oldalt fog váltani.
Másrészről, a rendezés után a prediktor először egy erősen nem vett állapotba kerül, és amikor az értékek magas értékre változnak, a prediktor három lépésben végigváltozik az erősen nem vettől az erősen vettig.
|
Ugyanebben a sorban (azt hiszem, ezt egyetlen válasz sem emelte ki) jó megemlíteni, hogy néha (különösen olyan szoftverekben, ahol a teljesítmény számít - például a Linux kernelben) találhat néhány, ha az alábbi kijelentéseket:
ha (valószínű (minden_is_ok))
{
/* Csinálj valamit */
}
vagy hasonlóan:
ha (valószínűtlen (nagyon_valószínűtlen_ feltétel))
{
/* Csinálj valamit */
}
A valószínű () és a valószínűtlen () is valójában olyan makrók, amelyeket úgy definiálunk, hogy valami hasonlót használunk, mint például a GCC __builtin_expect, hogy segítsen a fordítónak előrejelző kódot beilleszteni az állapot elősegítésére, figyelembe véve a felhasználó által szolgáltatott információkat. A GCC támogat más beépített programokat, amelyek megváltoztathatják a futó program viselkedését, vagy alacsony szintű utasításokat adhatnak ki, mint például a gyorsítótár törlése stb. Lásd ezt a dokumentációt, amely a rendelkezésre álló GCC beépített verzióit ismerteti.
Általában ez a fajta optimalizálás főleg a valós idejű hardveralkalmazásokban vagy beágyazott rendszerekben található meg, ahol a végrehajtás ideje számít és kritikus. Például, ha valamilyen hibaállapotot ellenőriz, amely csak 1/10000000 alkalommal fordul elő, akkor miért nem tájékoztatja erről a fordítót? Így alapértelmezés szerint az elágazás-előrejelzés feltételezi, hogy a feltétel hamis.
|
A C ++ rendszerben gyakran használt logikai műveletek sok ágat eredményeznek a lefordított programban. Ha ezek az ágak a hurkok belsejében vannak, és nehéz őket megjósolni, akkor jelentősen lelassíthatják a végrehajtást. A logikai változókat 8 bites egész számokként tárolják, 0 érték hamis és 1 hamis érték.
A logikai változók túlhatározottak abban az értelemben, hogy minden olyan operátor, amelynek logikai változói vannak bemenetként, ellenőrzi, hogy a bemeneteknek van-e más értéke, mint 0 vagy 1, de azok az operátorok, amelyeknek logikai kimenete van, nem eredményezhetnek más értéket, mint 0 vagy 1. A logikai változók inputként a szükségesnél kevésbé hatékonyak.
Tekintsük a példát:
bool a, b, c, d;
c = a && b;
d = a || b;
Ezt általában a fordító valósítja meg a következő módon:
bool a, b, c, d;
ha (a! = 0) {
ha (b! = 0) {
c = 1;
}
más {
goto CFALSE;
}
}
más {
CFALSE:
c = 0;
}
ha (a == 0) {
ha (b == 0) {
d = 0;
}
más {
goto DTRUE;
}
}
más {
DTRUE:
d = 1;
}
Ez a kód korántsem optimális. Az ágak téves előrejelzések esetén sokáig tarthatnak. A Boole-műveletek sokkal hatékonyabbá tehetők, ha biztosan tudjuk, hogy az operandusoknak nincs más értéke, mint 0 és 1. Az oka annak, hogy a fordító nem tesz ilyen feltételezést, az az, hogy a változóknak más értékeik is lehetnek, ha nem inicializáltak vagy ismeretlen forrásokból származnak. A fenti kód akkor optimalizálható, ha az a és b értékeket inicializáltuk érvényes értékekre, vagy ha azok logikai kimenetet előállító operátoroktól származnak. Az optimalizált kód így néz ki:
char a = 0, b = 1, c, d;
c = a & b;
d = a | b;
A char a bool helyett használatos annak érdekében, hogy lehetővé tegye a bitenkénti operátorok (& és |) használatát a logikai operátorok (&& és ||) helyett. A bitenkénti operátorok egyetlen utasítások, amelyek csak egy óraciklust vesznek igénybe. Az OR operátor (|) akkor is működik, ha a és b értéke 0 vagy 1 értéktől eltér. Az AND operátor (&) és az EXCLUSIVE OR operátor (^) inkonzisztens eredményeket adhat, ha az operandusok értéke 0-tól és 1-től eltérõ.
~ nem használható NEM. Helyette,megteheti a logikai értéket NEM egy olyan változóról, amelyről ismert, hogy 0 vagy 1, ha XOR'-val 1-el adjuk:
bool a, b;
b =! a;
optimalizálható:
char a = 0, b;
b = a ^ 1;
Az a && b nem helyettesíthető a & b-vel, ha b olyan kifejezés, amelyet nem szabad értékelni, ha a hamis (a && nem fogja értékelni a b-t és a akaratot). Hasonlóképpen, a || b nem helyettesíthető a | -val b, ha b olyan kifejezés, amelyet nem szabad értékelni, ha a igaz.
A bitenkénti operátorok használata előnyösebb, ha az operandusok változók, mint ha az operandusok összehasonlítások:
bool a; kettős x, y, z;
a = x> y && z <5,0;
az esetek többségében optimális (hacsak nem számít arra, hogy a && kifejezés sok elágazástévesztést generál).
|
Az biztos!...
Az elágazás előrejelzése lassabbá teszi a logikát a kódban bekövetkező váltás miatt! Olyan, mintha egyenes vagy sok kanyarral rendelkező utcára haladna, az biztos, hogy az egyenes gyorsabb lesz! ...
Ha a tömb rendezve van, akkor az Ön állapota az első lépésben hamis: data [c]> = 128, majd az utca végéig tartó teljes út valós értékévé válik. Így juthat el gyorsabban a logika végére. Másrészt válogatás nélküli tömb használatával sok fordításra és feldolgozásra van szükség, amelyek biztosan lassabban futtatják a kódot ...
Nézd meg az alábbi képet, amelyet neked készítettem. Melyik utca készül el gyorsabban?
Tehát programszerűen az elágazás-előrejelzés lassabbá teszi a folyamatot ...
Szintén a végén jó tudni, hogy kétféle elágazási előrejelzésünk van, amelyek mindegyike másképp fogja befolyásolni a kódot:
1. Statikus
2. Dinamikus
A mikroprocesszor először használja a statikus elágazás-előrejelzést
feltételes elágazással találkozunk, és a dinamikus elágazás-előrejelzés az
a feltételes ágkód sikeres végrehajtásához használják.
A kód hatékony megírása érdekében használja ki ezeket
szabályok, ha if-else vagy váltó utasításokat ír, ellenőrizze a legjobban
a leggyakoribb esetek, és fokozatosan dolgoznak a legkevésbé.
A hurkok nem feltétlenül igényelnek külön kódrendelést
statikus elágazás-előrejelzés, mivel csak a hurok-iterátor feltétele
általában használják.
|
Erre a kérdésre már sokszor kiváló választ adtak. Ennek ellenére még egy érdekes elemzésre szeretném felhívni a csoport figyelmét.
Nemrégiben ezt a (nagyon kissé módosított) példát használták arra is, hogy bemutassák, hogyan lehet egy kódrész profilozni magában a programban a Windows rendszeren. Útközben a szerző azt is megmutatja, hogyan lehet az eredményeket felhasználni annak meghatározására, hogy a kód hol tölti idejének nagy részét rendezett és rendezetlen esetben is. Végül a darab azt is bemutatja, hogyan lehet a HAL (Hardware Abstraction Layer) kevéssé ismert tulajdonságát felhasználni annak meghatározására, hogy mekkora elágazási tévedés történik a válogatás nélküli esetben.
A link itt található:
Az önprofil bemutatása
|
Amint azt mások már említették, a rejtély mögött a Branch Predictor áll.
Nem próbálok hozzáfűzni valamit, hanem más módon elmagyarázom a koncepciót.
Van egy tömör bevezetés a wikiben, amely szöveget és ábrát tartalmaz.
Tetszik az alábbi magyarázat, amely egy diagram segítségével intuitív módon kidolgozza az elágazási prediktort.
A számítógépes architektúrában az ág prediktor a
digitális áramkör, amely megpróbálja kitalálni, hogy az elágazás melyik irányba (pl
ha-akkor-más struktúra) megy, mielőtt ezt biztosan tudni lehet. Az
Az elágazás-előrejelző célja a
utasítás pipeline. Az ág-előrejelzők kritikus szerepet játszanak a
magas hatékony teljesítmény elérése számos modern csővezetékben
mikroprocesszoros architektúrák, például x86.
A kétirányú elágazást általában feltételes ugrással valósítják meg
utasítás. A feltételes ugrást vagy "nem lehet megtenni", és folytatni lehet
végrehajtás az azonnali kód első elágazással
a feltételes ugrás után, vagy lehet "venni" és ugrani a
más hely a program memóriájában, ahol a kód második elágazása van
tárolt. Nem biztos, hogy feltételes ugrás lesz-e
- vették vagy nem vették be, amíg a feltételt ki nem számolták és a
feltételes ugrás az utasítás végrehajtási szakaszán túljutott
csővezeték (lásd 1. ábra).
A leírt forgatókönyv alapján animációs bemutatót írtam, amely bemutatja, hogyan hajtják végre az utasításokat egy folyamatban különböző helyzetekben.
Fiókjósló nélkül.
Elágazás-előrejelzés nélkül a processzornak várnia kell a
A feltételes ugrás utasítás a végrehajtási szakaszon túlhaladt a
a következő utasítás beléphet a folyamat folyamatába.
A példa három utasítást tartalmaz, az első pedig feltételes ugrási utasítás. Ez utóbbi két utasítás a feltételes ugrás végrehajtásáig mehet a folyamatba.
A 3 utasítás végrehajtásához 9 óraciklus szükséges.
Használja a Branch Predictort, és ne végezzen feltételes ugrást. Tegyük fel, hogy a jóslás nem veszi afeltételes ugrás.
Három óra végrehajtása 7 óraciklusba kerül.
Használja a Branch Predictort, és végezzen feltételes ugrást. Tegyük fel, hogy a jóslás nem a feltételes ugrást hajtja végre.
A 3 utasítás végrehajtásához 9 óraciklus szükséges.
Az ágak téves megjóslása esetén elvesztegetett idő megegyezik
szakaszok száma a folyamatban a lekérési fázistól a
szakasz végrehajtása. A modern mikroprocesszorok általában elég hosszúak
csővezetékeket úgy, hogy a hibás előrejelzési késés 10 és 20 óra között legyen
ciklusok. Ennek eredményeként a csővezeték hosszabbá tétele megnöveli a
fejlettebb ág prediktor.
Amint láthatja, úgy tűnik, nincs okunk arra, hogy ne alkalmazzuk a Fiókjóslót.
Ez egy egészen egyszerű bemutató, amely tisztázza a Branch Predictor alapvető részét. Ha ezek a gifek idegesítőek, kérjük, távolítsa el őket a válaszból, és a látogatók az élő demo forráskódot is megkaphatják a BranchPredictorDemo-tól
|
Ág-előrejelzés nyereség!
Fontos megérteni, hogy az ágak hibás megjóslása nem lassítja a programokat. Az elmulasztott predikció költsége éppen olyan, mintha az ágra vonatkozó predikció nem létezne, és Ön megvárta a kifejezés kiértékelését, hogy eldöntse, milyen kódot futtasson (további magyarázat a következő bekezdésben).
if (kifejezés)
{
// 1. futás
} más {
// 2. futás
}
Ha van if-else \ switch utasítás, akkor a kifejezést ki kell értékelni, hogy meghatározzuk, melyik blokkot kell végrehajtani. A fordító által generált összeállítási kódban feltételes elágazási utasítások kerülnek beillesztésre.
Az elágazási utasítás a számítógépet egy másik utasítássorozat végrehajtásának megkezdéséhez vezethet, és így eltérhet az utasítások végrehajtásának alapértelmezett viselkedésétől (azaz ha a kifejezés hamis, a program kihagyja az if blokk kódját), bizonyos feltételektől függően, ami a kifejezésértékelés esetünkben.
Ennek ellenére a fordító megpróbálja megjósolni az eredményt, mielőtt azt ténylegesen kiértékelik. Az if blokkból kap utasításokat, és ha a kifejezés igaznak bizonyul, akkor csodálatos! Megszereztük a kiértékeléséhez szükséges időt, és előrehaladtunk a kódban; ha nem, akkor rossz kódot futtatunk, a csővezeték kiürül, és a megfelelő blokk fut.
Megjelenítés:
Tegyük fel, hogy ki kell választania az 1. vagy a 2. utat. Várva, hogy partnere ellenőrizze a térképet, megállt a ## helyen és várt, vagy csak választhatta az 1. útvonalat, és ha szerencséje volt (az 1. út a helyes útvonal), akkor nagyszerű, hogy nem kellett megvárnia, amíg a partnere ellenőrizte a térképet (megtakarította azt az időt, amelyre a térkép ellenőrzése kellett volna), különben csak visszafordul.
Míg a csővezetékek öblítése rendkívül gyors, manapság megéri ezt a szerencsejátékot megvenni. A válogatott vagy a lassan változó adatok előrejelzése mindig egyszerűbb és jobb, mint a gyors változások előrejelzése.
O 1. út / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
2. út \ --------------------------------
|
Az ARM-en nincs szükség ágra, mert minden utasításnak van egy 4 bites feltételmezõje, amely (nulla költség mellett) teszteli a processzor állapotregiszterében felmerülõ 16 különbözõ feltétel bármelyikét, és ha az utasítás feltétele hamis, az utasítás kihagyásra kerül. Ez kiküszöböli a rövid elágazások szükségességét, és ennek az algoritmusnak nem lenne elágazási előrejelzési találata. Ezért ennek az algoritmusnak a rendezett verziója lassabban fog futni, mint az ARM-ben a válogatás nélküli verzió, a rendezés extra költségei miatt.
Ennek az algoritmusnak a belső hurkja a következőképpen néz ki az ARM összeállítási nyelvén:
MOV R0, # 0 // R0 = összeg = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, data // R2 = adattömb addr (tegye ezt az utasítást a külső hurokba)
.inner_loop // Belső hurokág címke
LDRB R3, [R2, R1] // R3 = adatok [c]
CMP R3, # 128 // hasonlítsa össze az R3-at a 128-mal
R0, R0, R3 HOZZÁADÁSA // ha R3> = 128, akkor összeg + = adat [c] - nincs szükség ágra!
R1, R1, # 1 // c ++
CMP R1, #arraySize // c összehasonlítása az arraySize-el
BLT internal_loop // Elágazás a belső_loop felé, ha c  ());
for (aláíratlan c = 0; c  = 128
összeg = összeg + adatok1 (j);
vége
vége
vége
toc;
ExeTimeWithSorting = toc - tic;
A fenti MATLAB-kód eredményei a következők:
a: Eltelt idő (válogatás nélkül) = 3479,880861 másodperc.
b: Eltelt idő (válogatással) = 2377,873098 másodperc.
A C kód eredményei, mint a @GManNickG-ben:
a: Eltelt idő (válogatás nélkül) = 19,8761 sec.
b: Eltelt idő (válogatással) = 7,37778 mp.
Ez alapján úgy tűnik, hogy a MATLAB majdnem 175-szer lassabb, mint a C megvalósítás válogatás nélkül, és 350-szer lassabb a rendezésnél. Más szavakkal, az (elágazási előrejelzés) hatása 1,46x a MATLAB implementációnál és 2,7x a C implementációnál.
|
Nem helyes az a más válaszok feltételezése, miszerint az adatokat rendezni kell.
A következő kód nem a teljes tömböt, hanem csak annak 200 elemű szegmenseit rendezi, és ezáltal a leggyorsabban fut.
Csak a k-elem szakaszainak rendezése befejezi az előfeldolgozást lineáris időben, O (n), nem pedig a teljes tömb rendezéséhez szükséges O (n.log (n)) idő alatt.
#include 
#include 
#include 
int main () {
int adatok [32768]; const int l = az adatok mérete / az adatok mérete [0];
for (aláíratlan c = 0; c  = 128)
összeg + = adatok [c];
}
}
std :: cout << static_cast  (óra () - start) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum =" << sum << std :: endl;
}
Ez azt is "bizonyítja", hogy semmi köze semmilyen algoritmikus kérdéshez, például a rendezési sorrendhez, és valóban elágazás-előrejelzés.
|
Bjarne Stroustrup válasza erre a kérdésre:
Ez interjúkérdésnek hangzik. Ez igaz? Honnan tudnád? Rossz ötlet megválaszolni a hatékonysággal kapcsolatos kérdéseket anélkül, hogy néhány mérést elvégeznénk, ezért fontos tudni, hogyan kell mérni.
Tehát megpróbáltam egy millió egész vektorral, és kaptam:
Már rendezve 32995 ezredmásodperc
Megkeverve 125944 ezredmásodperc
Már rendezve 18610 ezredmásodperc
Megkeverve 133304 milliszekundum
Már rendezve 17942 ezredmásodperc
Megkeverve 107858 ezredmásodperc
Néhányszor futottam, hogy biztos legyek benne. Igen, a jelenség valóságos. A kulcs kódom a következő volt:
void run (vektor  & v, const karakterlánc és címke)
{
auto t0 = rendszer_óra :: most ();
sort (v.begin (), v.end ());
auto t1 = rendszer_óra :: most ();
cout << címke
<< duration_cast  (t1 - t0) .szám ()
<< "ezredmásodperc \ n";
}
érvénytelen tst ()
{
v vektor (1 000 000);
iota (v.begin (), v.end (), 0);
run (v, "már rendezve");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
futás (v, "összekevert");
}
Legalábbis a jelenség valóságos ezzel a fordítóval, a standard könyvtárral és az optimalizáló beállításokkal. A különböző megvalósítások különböző válaszokat adhatnak és adnak is. Valójában valaki elvégzett egy szisztematikusabb vizsgálatot (gyors internetes keresés talál rá), és a legtöbb megvalósítás ezt a hatást mutatja.
Az egyik ok az elágazás-előrejelzés: a rendezési algoritmusban a legfontosabb művelet az „if (v [i]  = 128. értékek érdekelnek. Ez azt jelenti, hogy könnyen kivonhatunk egyetlen bitet, amely megmondja, hogy akarunk-e értéket vagy sem: eltolással a jobb 7 bitből álló adatok, 0 vagy 1 bit marad, és csak akkor szeretnénk hozzáadni az értéket, ha 1 bitünk van. Nevezzük ezt a bitet "döntési bitnek".
Ha a döntési bit 0/1 értékét indexként használjuk egy tömbben, akkor olyan kódot készíthetünk, amely ugyanolyan gyors lesz, függetlenül attól, hogy az adatokat rendezik-e vagy sem. Kódunk mindig ad hozzá értéket, de ha a döntési bit 0, akkor hozzáadjuk az értéket valahol, ami nem érdekel. Itt van a kód:
// Teszt
óra_t indítás = óra ();
hosszú hosszú a [] = {0, 0};
hosszú hosszú összeg;
for (aláíratlan i = 0; i <100000; ++ i)
{
// Elsődleges hurok
for (aláíratlan c = 0; c > 7);
a [j] + = adat [c];
}
}
double elapsedTime = static_cast  (óra () - start) / CLOCKS_PER_SEC;
összeg = a [1];
Ez a kód elvesztegeti az összeadások felét, de soha nem rendelkezik elágazás-előrejelzési hibával. Rendkívül gyorsabb a véletlenszerű adatoknál, mint a tényleges if utasítással ellátott verzió.
De tesztelésem során az explicit keresőtábla ennél valamivel gyorsabb volt, valószínűleg azért, mert a keresőtáblába történő indexelés valamivel gyorsabb volt, mint a biteltolás. Ez megmutatja, hogy a kódom hogyan állítja be és használja a keresőtáblát (a kódban elképzelhetetlenül lut-nak hívják a "LookUp Table" -t). Itt van a C ++ kód:
// Nyújtsa be, majd töltse ki a keresési táblázatot
int lut [256];
for (aláíratlan c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// A felépítés után használja a keresőtáblát
for (aláíratlan i = 0; i <100000; ++ i)
{
// Elsődleges hurok
for (aláíratlan c = 0; c  érték)
csomópont = csomópont-> pBal;
más
csomópont = csomópont-> pRight;
ez a könyvtár valami hasonlót tenne:
i = (x  érték);
csomópont = csomópont-> link [i];
Ez egy szép megoldás, és talán sikerülni is fog.
|
Nagyon aktív kérdés. Nyerjen 10 hírnevet a kérdés megválaszolásához. A jó hírnév követelménye megvédi ezt a kérdést a spamektől és a nem válaszolóktól.
Nem a keresett válasz? Tallózzon a java c ++ teljesítményoptimalizálás ág-előrejelzéssel ellátott többi kérdésben, vagy tegye fel saját kérdését.